//  给定一个链表数组，每个链表都已经按照升序排列,要求，将所有链表合并到一个升序链表中，返回合并后的链表

// 思路：和归并排序思路一致，不断递归到链表数组长度为1，开始归并处理，合并链表
// 时间复杂度：O(nlogk)，n是所有链表的节点总数，k是链表的个数
// 空间复杂度：O(logk)，递归栈的深度

const { LinkedList, ListNode} = require('./64.设计链表')

function mergeKLists(arr) {
    if (!arr || !arr.length) {
        return null
    }
    function mergeSort(arr) {
        if (arr.length <= 1) {
            return arr[0]
        }
        let mid = Math.floor(arr.length / 2)
        let leftNode = mergeSort(arr.slice(0, mid))
        let rightNode = mergeSort(arr.slice(mid))
        return merge(leftNode, rightNode)
    }

    function merge(leftNode, rightNode) {
        let dummyHead = new ListNode(0, null)
        let cur = dummyHead
        while (leftNode && rightNode) {
            if (leftNode.val <= rightNode.val) {
                cur.next = leftNode
                leftNode = leftNode.next
            } else {
                cur.next = rightNode
                rightNode = rightNode.next
            }
            // 别忘了更新
            cur = cur.next
        } 
        cur.next = leftNode ? leftNode : rightNode
        return dummyHead.next
    }
    return mergeSort(arr)
}

let lists = [new LinkedList([1,4,5]).head, new LinkedList([1,3,4]).head, new LinkedList([2, 6]).head]
let result = mergeKLists(lists)
// let result = mergeKLists([])
console.log(result)